class Solution
{
public:
    // 两个dp数组，一个保存对于奇数要大于后一个数的情况
    // 一个保存对于奇数要小于后一个数的情况
    //
    enum
    {
        N = 40010
    };
    int maxTurbulenceSize(vector<int> &arr)
    {
        int f[N][2];
        int ans = 1;
        // 一定是连续的，并且不会出现重复的情况
        for (int i = 1; i <= arr.size(); ++i)
        {
            if (i == 1)
                f[1][0] = f[1][1] = 1;
            else
            {
                if ((i - 1) % 2)
                {
                    f[i][1] = arr[i - 1] > arr[i - 2] ? f[i - 1][1] + 1 : 1;
                    f[i][0] = arr[i - 1] < arr[i - 2] ? f[i - 1][0] + 1 : 1;
                }
                else
                {
                    f[i][1] = arr[i - 1] < arr[i - 2] ? f[i - 1][1] + 1 : 1;
                    f[i][0] = arr[i - 1] > arr[i - 2] ? f[i - 1][0] + 1 : 1;
                }
            }
            ans = max(ans, max(f[i][1], f[i][0]));
        }
        return ans;
    }
};